class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        n = len(triangle)
        f = [[0] * n for _ in range(n)]
        f[0][0] = triangle[0][0]
        for i in range(1, n):
            f[i][0] = f[i - 1][0] + triangle[i][0]
            for j in range(1, i):
                f[i][j] = min(f[i - 1][j - 1], f[i - 1][j]) + triangle[i][j]
            f[i][i] = f[i - 1][i - 1] + triangle[i][i]
        return min(f[n - 1])
'''
f[i][j]=min(f[i−1][j−1],f[i−1][j])+c[i][j]
f[i][0]=f[i−1][0]+c[i][0]
f[i][i]=f[i−1][i−1]+c[i][i]
'''

# 方法二空间优化
class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        n = len(triangle)
        f = [[0] * n for _ in range(2)]
        f[0][0] = triangle[0][0]
        for i in range(1, n):
            curr, prev = i % 2, 1 - i % 2
            f[curr][0] = f[prev][0] + triangle[i][0]
            for j in range(1, i):
                f[curr][j] = min(f[prev][j - 1], f[prev][j]) + triangle[i][j]
            f[curr][i] = f[prev][i - 1] + triangle[i][i]
        return min(f[(n - 1) % 2])
'''
f[i][j]=min(f[i−1][j−1],f[i−1][j])+c[i][j]
f[i][0]=f[i−1][0]+c[i][0]
f[i][i]=f[i−1][i−1]+c[i][i]
'''